/*
 * File:   node.h
 * Author: Stripped
 *
 * Created on April 18, 2009, 8:00 AM
 */

#ifndef _NODE_H
#define _NODE_H

#include <vector>
#include <utility>
#include <stdexcept>
#include "KeyValueEntity.h"
#include "InerNode.h"
#include <string>

using namespace std;

template <class TKey, class TValue>
class KeyValuePair;

template <class TKey, class TValue>
class InerNode;

template <class TKey, class TValue>
class Node {
    //typedef KeyValuePair<TKey, TValue> KeyValuePair;

public:

    /**
     * Constructor: Creates a Node
     *
     * @param  nodeMaxSize: is the max size of the node, default value = 2
     * @param  parent: node that will be parent of the new node, default value = NULL
     */
    Node(unsigned int nodeMaxSize, Node<TKey, TValue>* parent = NULL)
    {
        this->nodeMaxSize = nodeMaxSize;
        this->parentNode = parent;
        this->elements.reserve(nodeMaxSize +1);
    }

     /**
     * Destructor
     *
     */
    virtual ~Node() {}

    /**
     * Adds a key-value pair into the tree.
     *
     * Throws an std::logic_exception if the key exists in the tree.
     *
     * @param  TKey key which identifies the key-value pair
     * @param  TValue value of the key-value pair
     */
    virtual Node<TKey, TValue>* put(const TKey& key, const TValue& value) = 0;

    /**
     * Returns the value of a specified key
     *
     * Throws std::logic_error if the key does not exists
     *
     * @param  TKey key which value you wish to retrieve
     * @return TValue value which matches the given key
     */
    virtual TValue& get(const TKey& key) = 0;

    /**
     * Removes an element from the node.
     * NOTE: Since remove is only intended as part of an update, it does not fixes underflow after deletion.
     *
     * Throws std::logic_error if the key is not present
     *
     * @param key to remove
     */
    virtual void remove (const TKey& key) = 0;

    /**
     * Searchs for a specified key and returns true if exists
     *
     * @param  TKey key which value you wish to find
     * @return bool True if the key exists, False if it doesn't
     */
    virtual bool has(const TKey& key) const = 0;

    /**
     * counts the amount of elements in the node.
     *
     * @return returns the elements count
     */
    virtual unsigned int elementsCount() const = 0;

    /**
     * Swaps the element for the smaller in the node.
     *
     * @param element: KeyValuePair to swap
     * @return returns the old KeyValuePair that was replaced
     */
    virtual  KeyValuePair<TKey, TValue>  swap( KeyValuePair<TKey, TValue>  element) = 0;

    /**
     * Adds the element into the correct position. And retrns the position where it was aded
     *
     * @param the element to insert
     */
    unsigned int forceAddElement( KeyValuePair<TKey, TValue>  element)
    {
        typename std::vector< KeyValuePair<TKey, TValue> >::iterator it = this->elements.begin();
        unsigned int pos = 0;

        while ((it != this->elements.end()) && (*it < element))
        {
            it++;
            pos++;
        }

        this->elements.insert(it, element);

        return pos;
    }

     /**
     * Adds the element into the last position.
     *
     * @param the element to insert
     */
    void forcePushBackElement( KeyValuePair<TKey, TValue>  element)
    {
        this->elements.push_back(element);
    }

    /**
     * Adds the children into the correct position.
     *
     * @param Node<TKey, TValue>* the node children to insert.
     * @param unsigned int at the position in which to insert the node.
     */
    virtual void forceAddChildren(Node<TKey, TValue>* node, unsigned int at) {}

    /**
     * Adds the children into the correct position.
     *
     * @param Node<TKey, TValue>* the node children to insert.
     */
    virtual void forcePushBackChildren(Node<TKey, TValue>* node) {}

    /**
     * Fixes the overflow by splitting the current node and promoting the key in the middle
     *
     * @return returns the new parent node if any was created to fix the overflow
     */
    Node<TKey, TValue>* fixOverflow()
    {
        if (!this->isOverflow())
            return NULL;

        unsigned int at = 0;

         KeyValuePair<TKey, TValue>  element = this->elements.at(this->nodeMaxSize / 2);
        Node<TKey, TValue>* sibling = this->split();

        if (this->isRoot())
        {
            // TODO: verify how we can change this
            this->parentNode = new InerNode<TKey, TValue>(this->nodeMaxSize);

            this->parentNode->forcePushBackElement(element);

            this->parentNode->forcePushBackChildren(this);
            this->parentNode->forcePushBackChildren(sibling);

            sibling->parentNode = this->parentNode;

            //sibling->forceRemoveFirstElement();

            return this->parentNode;
        }
        else
        {
            at = this->parentNode->forceAddElement(element);

            this->parentNode->forceAddChildren(sibling, at + 1);

            //sibling->forceRemoveFirstElement();

            if (this->parentNode->isOverflow())
            {
                return this->parentNode->fixOverflow();
            }

            return NULL;
        }
    }

    /**
     * Removes the first element of the list
     *
     */
    virtual void forceRemoveFirstElement() = 0;

    /**
     * For debuggin purposes, it prints the tree
     *
     */
    //virtual void printNode() = 0;

    /**
     * Fills the vector sent as parameter with all the elements of the tree (recursive)
     *
     * @param vector to fill
     */
    virtual void getAllElements(std::vector< KeyValuePair<TKey, TValue> > &vector) = 0;

    void setParent(Node<TKey, TValue>* parentNode){
        this->parentNode = parentNode;
    }

protected:
    unsigned int nodeMaxSize;
    Node<TKey, TValue>* parentNode;
    std::vector< KeyValuePair<TKey, TValue> > elements;

    bool isRoot()
    {
        return (this->parentNode == NULL);
    }

    bool isUnderflow()
    {
        return (this->elements.size() < this->nodeMaxSize / 2);
    }

    bool isOverflow()
    {
        return (this->elements.size() > this->nodeMaxSize);
    }

    virtual Node<TKey, TValue>* split() = 0;

private:
    Node<TKey, TValue>(const Node<TKey, TValue>&) {};
    Node<TKey, TValue>& operator=(const Node<TKey, TValue>&) {};
};

#endif  /* _NODE_H */
